Skip to content

Kevin's Home

TwitterGithub

Basic Algorithms in Go

— algorithm, golang — 1 min read

最近学Go，感觉挺不错的。闲来无事用它写了几种常用的基础算法。

快排

思想很简单，实现起来为了方便每次以left作为基准，也可以使用BFS来节省递归栈：

最短路

最短路核心思想就是Relax操作。效率高的单源最短路有下面两种算法：

  1. Dijikstra，不能处理负权路,但是时间复杂度比较稳定.
  2. SPFA是我比较喜欢的一种算法，可以判断负权路。正常情况的时间复杂度为O(kE) 其中k<<V；最好的情况即一次BFS，时间复杂度为 O(E)，然而对于某些精心构造的图，复杂度可以达到Bellman-ford级别：O(VE)。 下面构图使用的是邻接表（适用于稀疏图），也可以用邻接矩阵（适用于稠密图）。

KMP

字符串匹配经典算法。关键在于维护一个这样的关系：x[i-next[i]...i-1]=x[0...next[i]-1]

To Be Continue...